class Solution {
public:
    vector<int> memo;
    int climbStairs(int n) {
        memo = vector<int>(n + 1, 0);
        return dp(n);
    }
    int dp(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (memo[n]) return memo[n];
        memo[n] = dp(n - 1) + dp(n - 2);
        return memo[n];
    }
};
